def binary_search_iterative(arr, target):
    """
    迭代实现的二分查找
    :param arr: 已排序的列表（升序）
    :param target: 要查找的目标值
    :return: 目标值的索引，如果不存在则返回-1
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
def binary_search_recursive(arr, target, left=0, right=None):
    """
    递归实现的二分查找
    :param arr: 已排序的列表（升序）
    :param target: 要查找的目标值
    :param left: 当前搜索范围的左边界
    :param right: 当前搜索范围的有边界
    :return: 目标值的索引，如果不存在则返回-1
    """
    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1


    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

def binary_search_recursive(arr, target, left=0, right=None):
    """
    递归实现的二分查找
    :param arr: 已排查的列表（升序）
    :param target: 要查找的目标值
    :param left: 当前搜索范围的左边界
    :param right: 当前搜索范围的右边界
    :return: 目标值的索引，如果不存在则返回-1
    """
    if right is None:
        right = len(arr) - 1

    if left > right:
        return -1

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target,left, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


def binary_search_reacursive(arr, target, left=0, right=None):
    """
    递归实现的二分查找
    :param arr: 已排序的列表（升序）
    :param target: 要查找的目标值
    :param left: 当前搜索范围的左边界
    :param right: 当前搜索范围的有边界
    :return: 目标的索引，如果不存在则返回-1
    """
    if right is None:
        right = len(arr) - 1

    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)




import time
import random

def compare_search_performance(list_size, target_position='middle'):
    """
    比较两种查找算法的性能
    :param list_size: 列表大小
    :param target_position: 目标位置('first', 'middle', 'last', 'random','nonexistent')
    """


    test_data = sorted([random.randint(0,10000000000) for _ in range(list_size)])

    if target_position == 'first':
        target = test_data[0]
    elif target_position == 'middle':
        target = test_data[len(test_data) // 2]
    elif target_position =='last':
        target = test_data[-1]
    elif target_position == 'random':
        target = random.choice(test_data)
    else:
        target = -1

    print(f"\n测试列表大小： {list_size:,} 元素")
    print(f"目标位置： {target_position}")

    start = time.perf_counter()
    result = linear_search(test_data, target)
    linear_time = time.perf_counter() - start
    print(f"线性查找： 结果={result}， 耗时={linear_time:.6f}秒")

    start = time.perf_counter()
    result = binary_search_iterative(test_data, target)
    binary_iter_time = time.perf_counter() -start
    print(f"迭代二分查找： 结果={result}， 耗时={binary_iter_time:.6f}秒")


    if linear_time > 0 and binary_iter_time >0:
        ratio =linear_time / binary_iter_time
        print(f"迭代二分查找比线性查找快 {ratio:.1f} 倍")



compare_search_performance(10_000,'middle')


compare_search_performance(100_000,'last')


compare_search_performance(100_000,'random')



compare_search_performance(1_000_000,'nonexistent')















